Již od počátku byla obec označována dvěma názvy. Český Újezd vyjadřoval způsob založení vesnice a celého panství pánů z Újezda ve 13.století, kdy některý z Bavorů ze Strakonic daroval svému družiníkovi pozemkový majetek s vesnicemi mezi Vltavou a Malší, jehož velikost byla stanovena objetím - ujetím na koni po hranicích, odtud tedy Újezd. Desítky vesnic se stejným základem názvu dokládají, že to byl zcela běžný způsob vzniku nových osad v dobách vnitřní kolonizace země. Nová vesnice měla již od 13.století také souběžně užívaný německý název - Steinkirchen (kamenný kostel). Dosud dominantní stavba v rámci obce poutala pozornost právě díky materiálu a dokládá, že sakrální stavby z kamene na počátku 13.století byly v této oblasti spíše vyjímkou. Pro odlišení od ostatních Újezdů v Čechách sloužily poukazy na polohu u Budějovic, na panství krumlovské a v archivních pramenech nám k bezpečnému odlišení napomáhá právě německé označení Steinkirchen. S rozvojem společnosti, obchodu a výměny informací bylo potřeba název zpřesnit, a tak v 19.století začíná být za jméno Újezd přikládáno Kamenný, podle charakteru středověkého kostela. Název se později ustálil v nynější podobě Kamenný (kostel) Újezd, německý tvar Steinkirchen byl naposledy užíván během druhé světové války v letech 1939 - 1945.

V první polovině 13.století bylo mezi Vltavou a Malší vyměřeno panství rytířů z Újezda, kteří měli v erbu znamení střely. První písemný doklad existence je z roku 1263, kdy je Vernéř z Kamenného kostela (Wernherus de Steynchirchen) svědkem při založení kláštera Zlatá Koruna. Téhož roku svědčí Michal z Újezda (Michael de Wgezt) při prodeji vesnice Záhoří klášteru ve Vyšším Brodě. Při obchodní cestě do Rakous vznikla u křižovatky vesnice s velkou obdélnou návsí, kostelem a tvrzí. Rytíři z Újezda sídlili nejdříve v tvrzi u kostela, po polovině 14.st., v době největšího rozmachu si zbudovali západně od vesnice na skále nad Vltavou hrad Maškovec. Postupně však chudli a dědickými podíly bylo panství zmenšováno a ve 20.letech 15.století se někteří členové poslední známé generace rodu živili také přepadáváním kupců na obchodní cestě kolem Újezda. Ve 30.letech 15.st. získávají část a roku 1455 zbylý majetek s vesnicí Rožmberkové, kteří tak úspěšně pokračují ve scelování svého dominia.
Během doby došlo k rozvoji a sloučení dvou vsí - Češnovice a Libský s Újezdem. Vesnice těžila z obchodního ruchu a užívala, i když zřejmě právně nepodloženě statut poddanského městečka a to až do roku 1464, kdy vyvrcholil spor ohledně mílového práva a vesnice spadla pod obchodní vliv a omezení řemesel městem Budějovic. Tehdy bylo v Újezdě 5 sladoven, 24 krčem a domů, kde se šenkovalo pivo a nejméně tři hostince. Bez překážek jako staletí před tím tu pracovali řezníci, krejčí, ševci, tkalci, hrnčíři, provazníci a kováři. Došlo ke kuriózní situaci, ač byl Újezd majetkem Rožmberků, pivo sem bylo dováženo z města, nebo jej tu vařili a prodávali budějovičtí poddaní. Situaci, kdy měl zisk z poddaných někdo jiný, se Rožmberkové snažili zvrátit žádostí o povýšení Újezda na město roku 1552. Pokus byl neúspěšný a Rožmberkové své aktivity realizovali na hranici mílového práva v blízké Plavnici, kde roku 1564 postavil Jakub Krčín z Jelčan dvůr s pivovarem, aby újezdští kupovali pivo své vrchnosti. V roce 1579 byly v Plavnici napuštěny nové rybníky a vznikl tu mlýn.
Roku 1602 získal krumlovské panství i s Újezdem císař Rudolf II. Za třicetileté války byla ve vsi vypálena a opuštěna polovina usedlostí. Hlavní silnice, která byla v dobách míru zdrojem zisku a prosperity, se během kruté války stala příčinou úpadku, neboť přivedla stavovská či císařská vojska, jenž bezohledně drancovala malá hospodářství. V roce 1622 získal krumlovské panství kníže Jan Oldřich z Eggenberka a roku 1719 přechází do majetku Schwarzenbergů. Roku 1849 se Kamenný Újezd stal samostatnou obcí a od 1.listopadu 1975 spravuje tyto obce - Březí, Bukovec, Radostice, Rančice, Opalice, Kosov, Krasejovka a Milíkovice.