Punkove wrestlingové začiatky sa odohrávali v malej organizácii s názvom Lunatic Wrestling Federation, kde prišiel v polovici 90. rokov aj so svojim bratom Mikeom. V tomto období začal používať meno CM Punk. Stalo sa tak po tom, ako vytvoril so CM Venomom spoločný tag tím s názvom Chick Magnets. Na rozdiel od svojich priateľov sa chcel stať profesionálom a vo wrestlingu videl niečo viac ako iba zdroj zábavy. Lunatic Wrestling Federation musel opustiť po tom, čo jeho brat spreneveril tisícky dolárov patriacich spoločnosti. Mike odvtedy už nezápasil.
Onedlho sa zapísal ako študent na wrestlingovú školu „Steel Domination“, ktorá sídlila v jeho rodnom Chicagu. Počas tohto obdobia ho trénovali Ace Steel, Danny Dominion a Kevin Quinn, ktorí mali veľkú zásluhu na tom, že sa z neho stal profesionálny wrestler. V rámci tréningového procesu Punk zápasil v St. Paul, Minnesote. Tu sa stretol so Scottom Coltonom, neskôr známym ako Colt Cabana. Stali sa z nich najlepší priatelia v reálnom živote a spoločne strávili veľkú časť svojich profesionálnych začiatkov. Obaja pôsobili na nezávislej scéne, či už ako spojenci alebo nepriatelia. Počas pôsobenia v Steel Domination vytvorili s Chuckee Smoothom, Adamom Pearceom a manažérom Daveom Prazakom alianciu s názvom Gold Bond Mafia.
Dôležitým momentom Punkovej kariéry bolo pôsobenie v Independent Wrestling Association: Mid-South (IWA:Mid-South). Počas tohto obdobia viedol spory s Coltom Cabanom a Chrisom Herom a stal sa jednou z hviezd spoločnosti. Dva razy získal IWA Mid-South Light Heavyweight Championship a päťkrát IWA Mid-South Heavyweight Championship. Medzitým porazil osobnosti ako A.J. Styles, Cabana a taktiež Eddieho Guerrera. Počas sporu s Chrisom Herom absolvoval 55-minútový TLC zápas, 93-minútový Two out of three falls zápas a niekoľko 60-minútových zápasov. Punkove zápasy počas sporu s Cabanom viedli k jeho odchodu do Ring of Honor. Od februára 2003 do mája 2004 odmietol zápasiť pre IWA:Mid South, na protest proti zlému zaobchádzaniu prezidenta spoločnosti Iana Rottena s Chrisom Herom. Hero bol ale presvedčený, že má na to iné dôvody a Rotten tvrdil, že je to iba výhovorka, aby mohol odísť zo spoločnosti. Napokon sa do IWA:Mid South predsa len vrátil ako wrestler a komentátor. Pre IWA:Mid South pracoval až do roku 2005, kedy podpísal zmluvu s World Wrestling Entertainment. Jeho posledné vystúpenie sa uskutočnilo 2. júla 2005, keď absolvoval hodinový zápas proti Deliriousovi, ktorý sa skončil remízou.