Мэдисон тарихы 1836 жылы бұрынғы федералды судья және жер алыпсатары Джеймс Дуэйн Доти Мендота және Монона көлдерінің арасындағы көркем мойнақтан жер телімін сатып алған кезде басталды. Қала «қағаз бетінде» жобаланып, сол жылы қайтыс болған АҚШ-тың төртінші президенті Джеймс Мэдисонның құрметіне аталды. Елді мекен іс жүзінде әлі болмағанына қарамастан, Дотидің белсенді лобби жасауының және стратегиялық тиімді орналасуының арқасында, Мэдисон 1836 жылы 28 қарашада жаңадан құрылған Висконсин Территориясының астанасы болып таңдалды. Бірінші Капитолийдің құрылысы 1837 жылы басталды.
Мэдисонның өсуі мен дамуы бірнеше шешуші факторларға байланысты болды. Оның саяси мәртебесі негізгі рөл атқарды: басынан бастап Мэдисон әкімшілік орталық ретінде дамыды, ал 1848 жылы Висконсин штатының астанасы мәртебесін алу оның маңыздылығын түпкілікті нығайтты. Ірі көлдер арасындағы тар мойнақтағы бірегей географиялық орналасуы да кем емес маңызды болды, бұл XIX ғасырда стратегиялық тұрғыдан тиімді еді. Қала тарихындағы бетбұрыс сәт 1848 жылы Висконсин университетінің негізі қалануы болды, ол Мэдисонды аймақтың ірі мәдени, ғылыми және экономикалық орталығына тез айналдырды. Сонымен қатар, 1854 жылы Мэдисонды Милуокимен байланыстыратын теміржолдың тартылуы урбанизация мен сауданы айтарлықтай жеделдетіп, шағын кентті толыққанды қалаға айналдырды.
Өмір сүруінің алғашқы онжылдықтарында Мэдисон экономикасы үкімет ғимараттарының құрылысымен және оларға қызмет көрсетумен тығыз байланысты болды. Университеттің ашылуымен қала зияткерлік және мәдени орталық ретінде беделге ие бола бастады. Сонымен қатар, көршілес Дейн округінің құнарлы жерлерінен алынатын ауылшаруашылық өнімдерін өңдеуге бағытталған өнеркәсіп дамыды. 1856 жылға қарай Мэдисон қала мәртебесін алған кезде, оның халқы 6 800 адамнан асты, бұл оның әкімшілік жобадан жанданып келе жатқан қала орталығына тез айналғанын көрсетеді.