The earliest sefardic siddur dates back to the 800's, see Is there a free copy of this early (earliest?) siddur online?. What is the oldest ashkenaz siddur, and it is available on the web or for purchase?
Machzor Vitry by Rabbi Simcha ben Shmuel of Vitry was written around the year 1100. It is not only a high-holiday machzor, but also contains the services for weekdays, Shabbat, and festivals, and customs and laws following the rulings of Rashi. Rav Simcha was a talmid of Rashi, and the machzor reflects the customs of Jews in early medieval France. This is believed to be the basis for Nusach Ashkenaz. A two-volume printed edition of it can be purchased here (it says three volumes, but I think it is really two). An online edition can be found here. Be warned though that some manuscripts and printed editions of this book have extraneous material added in and do not mark those as later additions not by Rav Simcha.