The move follows concerns that current exams fail to stretch the able and do not encourage them to go on to A-level.
Pupils will have the option of sitting a GCSE as hard as existing ones, plus a second which the exams watchdog says will assess maths from a "more abstract and structural perspective".
All pupils will take the conventional maths GCSE, which they must pass at C or better for their achievement to count in the main school league-table rankings.
Ms Kelly made the announcement to mark the second anniversary of the publication of the Smith report on maths teaching, which highlighted the "crisis" facing the subject.
Professor Adrian Smith, president of Queen Mary college, London, recommended that pupils sit two GCSEs in maths to reflect the extra time that many spent studying the subject.
Ms Kelly told a meeting at London's Royal Society: "This will be a major step to ensure that schools prioritise maths at key stage 4 and that pupils are challenged."
Ken Boston, chief executive of the Qualifications and Curriculum Authority, said the move was "significant and welcome".
Countries which were outperforming England in maths studies had a more challenging curriculum for able students, he said. Professor Smith also backed the new GCSE.
Sir Peter Williams, chair of the Advisory Committee on Mathematical Education, supported the move. But he said: "The new GCSE should not eat into the time allocated to the current GCSE, and changes should be piloted."
Dr Boston said that ministers might consider making all A-levels harder, following concerns about high numbers of A grades. The TES revealed last month that the QCA is thinking of introducing harder A-level questions in response to universities' concerns about how to select undergraduates.