Sonofons historie tager sin begyndelse i 1991, hvor virksomheden grundlægges og bliver den første udfordrer på det danske telemarked efter Folketingets afgørelse om liberalisering af telemarkedet - og derved en udlicitering af nye GSM900-mobillicenser. Dette sker som følge af det daværende EF’s beslutning om at liberalisere det europæiske marked for telefoni.
GN Store Nord (DK) og BellSouth (USA) grundlægger Sonofon i september 1991 sammen med to mindre aktionærer. I marts 1992 gennemføres de første mobilsamtaler på det nye GSM-net, og Sonofon går i kommerciel drift i juli 1992 og påbegynder salget af mobilabonnementer. Hovedsædet placeres i Aalborg, fordi byen huser et særdeles innovativt miljø inden for telekommunikationsområdet grundet den høje standard af ingeniører fra Aalborg Universitet. Sonofon bliver i april 1994 verdens første teleselskab til at gennemføre et mobilt dataopkald.
I løbet af de næste år etablerer Sonofon sig på mere end 20 adresser landet over. Hen mod slutningen af årtiet vælger man at have hovedsæde i København. Det nye hovedsæde tages i brug på Frederikskaj i København i april 1999. I sommeren 2000 overtager den norske telekoncern Telenor Group GN Store Nords aktieandel i Sonofon for 13,1 milliarder kroner.
I 2001 runder Sonofon en million kunder, og staten vælger Sonofon til at varetage al mobil- og fastnettelefoni i statens institutioner i de kommende to år. Der er tale om det største samlede køb af telefoni nogensinde, og kontrakten bringer Sonofons markedsandel på erhverv op på næsten 40 procent.
I december 2003 køber Telenor Group den resterende ejerandel af Sonofon fra BellSouth og bliver således eneejer af Sonofon. Over de næste år bliver også CBB og Cybercity en del af norske Telenor Group, der også ejer Canal Digital. Telenor Group har planer om et bredt nordisk samarbejde. I slutningen af 2005 køber Sonofon en 3G-licens og styrker derved sin plads blandt fremtidens teleudbydere i Danmark. I løbet af de næste par år udvider Sonofon sit distributionsnetværk betydeligt ved bl.a. at indgå aftaler om at sælge selskabets produkter i en række Føtex og Expert-butikker. Selskabet introducerer produkter som Yndlingsnummer (overflytning af fastnetnummer til mobilen) og mobilt bredbånd, der tilsammen støtter op om en samlet strategi, der lyder på at tilskynde brugen af mobile løsninger frem for fastnet. I 2009 lægges Sonofon sammen med Cybercity i én forretning under navnet Telenor i Danmark.