The changes mean elections originally set for April could take place in January.
|President Goodluck Jonathan has not yet declared if he will stand for election|
Nigeria’s House of Representatives must still give its approval to the changes.
The new date is intended to allow any legal challenges after the election to be settled before the new president takes office in May.
Correspondents say the announcement puts pressure on President Goodluck Jonathan – both to declare if he will run, and to push through reforms to ensure fair elections.
Senators backed a proposal to hold the general election “not earlier than 150 days and not later than 120 days before the expiration of the term of office” of either the president or a state governor.
Under the current rules, polls must be held between 30 and 60 days before the new president’s term begins.
Nigerian presidents take office on 29 May.
Attahiru Jega, the head of Nigeria’s electoral commission, said the election could be held some time between 8 and 15 January if the constitutional changes became final.
Nigeria has a long history of electoral fraud, and courts are still dealing with disputes over the April 2007 poll. International observers said the election was seriously flawed.