לפני הגעתם של האירופאים, הילידים בני האוהלון שהתגוררו לאורך החופים, בחצי האי סן פרנסיסקו; בני פויצ'ון אוהלון Puichon Ohlone התגוררו באזור פאלו אלטו. האזור של פאלו אלטו המודרנית תועד לראשונה על ידי משלחת פורטולה בהנהגתו של גאספאר דה פורטולה בשנת 1769. המשלחת יצאה מסן דייגו למונטריי. במשלחת היו 63 איש ו- 200 סוסים. כתוצאה מטעות בניווט בחסות הערפל המשלחת עקפה את מונטריי. כשהגיעו לאזור בו נבנתה מאוחר יותר העיר פסיפיקה , אנשי המשלחת עלו על רכס סוויני וראו את מפרץ סן פרנסיסקו. מרכס סוויני אנשי משלחת פורטולה ירדו לדרום-מזרח לאורך נחל סן אנדראס ולאורך נחל לגונה (הידוע גם בשם מאגר קריסטל ספרינגס ), משם עד קו פרשת המים של נחל סן פרנסיסקיטו קריק . בסופו של דבר הוקם מחנה המשלחת בין התאריכים 6–11 בנובמבר 1769, על יד עץ סקויה גבוה שלימים נודע בשם אל פאלו אלטו. מתוך מחשבה שהמפרץ רחב מאוד ולא ניתן לעבור אותו, המשלחת חזרה למונטריי.
בשנת 1777 הקים האב ג'וניפרו סרה את המיסיון סנטה קלרה דה אסיס , שגבולו הצפוני היה נחל סן פרנסיסקיטו ובאדמותיו כללו את פאלו אלטו המודרנית. האזור היה בשליטת מלך מקסיקו שיה כפוף למלך ספרד. ב־29 בנובמבר 1777 הוקמה העיר סן חוזה (העיר סן חוזה נמצאת כמה קילומטרים מדרום לפאלו אלטו) המושל של העיר היה המשנה למלך מקסיקו למורת רוחו של המיסיון והמתיישבים המקומיים. בשנת 1821 הסתיימה מלחמת העצמאות המקסיקנית ומקסיקו הפכה למדינה עצמאית. בשלב זה סן חוזה לא הכירה יותר בשלטון של מקסיקו עד 10 במאי 1825. מאידך, מקסיקו המשיכה למכור או להעניק הרבה מהאדמות שלה באזור.
במהלך מלחמת מקסיקו-אמריקה, ארצות הברית תפסה את אלטה קליפורניה בשנת 1846; רק ב־4 ביולי 1848, לאחר שנחתם חוזה גואדלופה הידאלגו חוקי ארצות הברית נכנסו לתוקף על אלטה קליפורניה. אזרחי מקסיקו באזור יכלו לבחור להיות אזרחי ארצות הברית והקרקעות שהוענקו להם על ידי מלך מקסיקו הוכרו כשייכים להם אם יבחרו בכך (עם הזמן נוצרו סכסוכים משפטיים רבים בעניין זה).
בשנת 1841, השטח של, ראנצ'ו רינקונדה דל ארויו דה סן פרנסיסקיטו , בגודל של כ־9 קילומטרים רבועים בחלקים התחתונים של נחל סן פרנסיסקיטו (שהם, חלקים מהעיר פארק מנלו המודרנית וחלק מצפון פאלו אלטו) ניתנו למריה אנטוניה מסה. היא ובעלה רפאל סוטו (שנפטר בשנת 1839) התיישבו בשנת 1835 באזור שליד הכבישים הנוכחיים ניואל ומידלפילד Newell ו- Middlefield והקימו חנויות לממכר ציוד ואספקה. בשנת 1839 נישאה בתם מריה לואיסה סוטו (1817–1883) לג'ון קופינגר, שהיה אמור להיות, בשנת 1841, היורש של השטח שנקרא ראנצ'ו קנאדה דה ריימונדו (במחוז סן מטאו המודרני). עם מותו של קופינגר בשנת 1847, ירשה אותו אשתו מריה ובהמשך התחתנה עם רב החובל שהגיע לביקור בשם, ג'ון גריר. ג'ון גריר בעצמו היה בעל נחלה משלו באזור שבין הרחובות Embarcadero ו- El Camino Real. שדרות גריר ובית המשפט נקראים על שמו.
מדרום לשטחים של משפחת סוטוס, האחים Secundino ו- Teodoro Robles רכשו בשנת 1849 את ראנצ'ו רינקון דה סן פרנסיסקיטו מידי ז'וזה פניה, שזכה בהם בשנת 1841. השטחים שהוענקו על ידי הספרדים באמצעות מלך מקסיקו הגיעו בדרום עד ראנצ'ו פסטוריה דה לאס בורגאס שהיו שייכים למריאנו קסטרו מעבר לכביש סן אנטוניו. מאוחר יותר שם החווה שונה לרובלס ראנצ'ו, המהווה כ-80% מפאלו אלטו ואוניברסיטת סטנפורד. בשנת 1863 לאחר דיונים בבתי המשפט השטח צומצם ל־28.25 קילומטרים רבועים. האחוזה (אסיינדה) הגדולה נבנתה על אדמתו של ז'וזה פניה ליד בפינה הרחובות פרן ודרך סן אנטוניו ובאמצע הדרך בין מידלפילד לרחוב עלמה. באחוזה אירחו פסטיבלים וקרבות שוורים. האחוזה נהרסה ברעידת האדמה שהייתה בסן פרנסיסקו (1906). העצים ששימשו לבניית האחוזה שימשו אחר כך לבניית אסם גדול בקרבת מקום, האסם שרד עד תחילת שנות החמישים של המאה העשרים. ב־10 באפריל 1853, אלישע אוסקר קרוסבי, רכש תמורת 2000 דולרים, שטח של קילומטר מרובע, הכולל את פארק הברון המודרני, נחל מטדרו ופארק העסקים סטנפורד. הוא קרא לנכס החדש שלו חוות מייפילד. מאוחר יותר נקשר שמה של חוות מייפילד לקהילה שהוקמה בסמוך לחווה. ב־23 בספטמבר 1856 הועברה אדמת קרוסבי לשרה וואליס כדי לפצות אותה על חוב שאלישע אוסקר קרוסבי, היה חייב לה. בשנת 1880, סקונדינו רובלס, אב לעשרים ותשעה ילדים, עדיין התגורר דרומית לפאלו אלטו, בסמוך למיקום שבו ממוקם מרכז הקניות סן אנטוניו של ימינו במאונטיין ויו.
רבים מהשמות הספרדיים באזור פאלו אלטו מייצגים את המושגים והמורשת המקומית, שהתושבים לשעבר השתמשו בהם. הרחובות פנה קורט, שדרות מירנדה, שהם בעצם הכביש המהיר פוטהייל , היו שמות הנשואין של חואנה בריונס וגם שמה כפי שמופיע בבתי משפט ובשדרות ובשמות רחובות אחרים בפאלו אלטו ובמאונטיין ויו הנמצאים על שטח שהיה בבעלותה כולל שטחים נרחבים בין אוניברסיטת סטנפורד, ורחוב גרנט.
העיירה מייפילד הוקמה בשנת 1855, סביב אתר תחנת הדיליז'נסים והפונדק המכונה "בקתת הדוד ג'ים" ליד צומת הרחובות אל קמינו ריאל ושדרת קליפורניה של ימינו בדרום פאלו אלטו. באוקטובר 1863 נבנתה מסילת הרכבת בין סן פרנסיסקו לסן חוזה. שירות הרכבות עד סן חוזה החל בינואר 1864. רחוב אל קמינו הפך לרחוב הראשי; הרחובות הצולבים מצפון-מזרח לדרום נקראו על שם גיבורי מלחמת האזרחים. שדרת קליפורניה הייתה במקור רחוב לינקולן. לעיירה היה עיתון משלה בשנת 1869 בשפות אנגלית וספרדית. בשנת 1903, היו בעיר מבשלות בירה ומפעל שימורים.
בשנת 1875, איש הכספים הצרפתי ז'אן בפטיסט פאולין קפרון, הידוע יותר בשם פיטר קוטס, רכש קרקעות במייפילד ובארבע מקומות נוספים סביב שכונת קולג' טרס שבפאלו אלטו של ימינו - יותר מאלף דונם המשתרעים מכביש פאייג' מיל של היום לרחוב סרה. קוטס כינה את רכושו חוות איירשייר. מגדל הלבנים המהולל בגובה 15 מטר ליד נחל מטדרו סימן ככל הנראה את הפינה הדרומית של נחלתו. בשנת 1876 לילנד סטנפורד האב החל לרכוש אדמות באזור עבור חוות סוסים, שנקראה חוות פאלו אלטו. סטנפורד רכש את חוות איירשייר בשנת 1882. בשנת 1891 הוא ואשתו ג'יין הקימו את אוניברסיטת סטנפורד, שהוקדשה לבנם לילנד סטנפורד ג'וניור , שמת מטיפוס הבטן בגיל 15 בשנת 1884. בשנת 1886 הוא הציע להקים את האוניברסיטה במייפילד. עם זאת, היה לו תנאי אחד: היה צריך לאסור אלכוהול מהעיירה. העיר מייפילד, שהייתה ידועה בשלוש המסבאות הסוערים שלה, דחתה את בקשתו. הסרוב לבקשתו מטעם עיריית מייפילד הביא אותו להקים את האוניברסיטה בעיר טמפרנס temperance town בעזרת חברו טימותי הופקינס מחברת מסילת הברזל הדרומית של האוקיינוס השקט, שקנה בשנת 1887 שלושה קלומטרים רבועים של קרקע פרטית עבור העיר החדשה. השטח שהופקינס רכש, היה תחום בשדרות אל קמינו ריאל, נחל סן פרנסיסקיטו, ברחובות בויס, צ'אנינג, מלוויל, שדרות הופקינס ודרך אמברקדרו. בשנת 1994 הוכרז השטח שהופיקנס רכש כמחוז מורשת מקומי במהלך אירועי המאה שנה לפאלו אלטו. סטנפורד הקים את האוניברסיטה שלו, אוניברסיטת סטנפורד ואת תחנת הרכבת של פאלו אלטו (בשדרת האוניברסיטה) ליד העיר החדשה שלו. תחילה נקראה האוניברסיטה החדשה אוניברסיטת פארק . בשנת 1894 האוניברסיה נכללה בתחום המוניציפלי של פאלו אלטו. בתמיכת סטנפורד, פאלו אלטו גדלה לעיר בגודל של מייפילד. בינואר 1905 לאחר סכסוכים ממושכים בתוך מייפילד הרשות המקומית קבלה החלטה לאסור קיום מסבאות ופאבים בעיר. ב־2 ביולי 1925, אישרו תושבי פאלו אלטו את סיפוח מייפילד ושתי הערים אוחדו רשמית ב־6 ביולי 1925. כתוצאה מכך יש בפאלו אלטו שני אזורים במרכז העיר: אחד לאורך שדרת האוניברסיטה ואחד לאורך שדרת קליפורניה.
העיתון מייפילד ניוז כתב הספד משלו כעבור ארבעה ימים:
עם תחושת חרטה עמוקה אנו רואים ברחובותינו היום את אלה שמוכרים, או נותנים, את העיר הקטנה והיפה שלנו לקהילה חיצונית. ראינו את מייפילד גדלה מכפר קטן, כשפאלו אלטו לא הייתה אלא שחת על שחת, לגודלה הנוכחי... ובתחושת צער אנו שוקלים את העובדה שיש מי שימכור או ימסור את העיר.
פאלו אלטו המשיכה לספח עוד אדמות, כולל את אזור מרכז הקניות סטנפורד בשנת 1953. פארק המחקר סטנפורד , דרך Embarcadero צפונית מזרחית לביישור Bayshore, ואזור West Bayshore / San Antonio Road סופחו במהלך שנות החמישים של המאה העשרים. שטחי אדמה גדולים ממערב לכביש המהיר פוטהייל סופחו בין השנים 1959 - 1968. הסיפוחים הגדולים האחרונים היו של פארק בארון Barron Park בשנת 1975 וב־1979 שטח גדול של ביצות הגובלות במפרץ סן פרנסיסקו.