There were three major histories (WSJ, NYT and Wired) of iPhone development that came out using interviews with AT&T and possibly Apple folk.
From them and other sources we get the following basic timeline:
... 2004 - Apple works with Motorola, who creates the failed ROKR.
Feb 2005 - Apple approaches Cingular about making their own phone.
Mid 2005 - Apple approaches Verizon.
Fall 2005 - UI dummies created on iPods. Some in Apple argue for Linux.
Nov 2005 - iPhone specific hardware development begins.
Jan 2006 - Mobile port of OSX begins.
Mid 2006 - Apple gives up on Verizon, signs exclusive with Cingular.
Nov 2006 - Jobs tells his staff they don't have a product yet.
Dec 2006 - Cingular CEO shown iPhone.
Jan 2007 - World shown iPhone.
So yes, the iPhone itself was created in a remarkably short time.
As for the idea that the iPad came first, Jobs did not say that at all. He said he saw an internal R&D touch-based tablet UI that made him want to do a similar thing for phones. The iPad itself is an outgrowth of what was done for the iPhone.
Technically apple didn't make the first iphone by themselves, most of the "phone" stuff was made by companies that already made phones.