Spodnia część doliny, wycięta w skałach osadowych została ukształtowana przez Potok Kościeliski. Górna część to strefa skał krystalicznych. Dolina przecina leżące w poprzek różne pasma skalne o odmiennej odporności, dzięki czemu powstały polany oraz przewężenia zwane bramami. Wiele tu ciekawych form skalnych, charakterystycznych dla skał wapiennych - ich nazwy w rodzaju Zbójnicki Stół, Zbójnickie Okna, Zbójnickie Turnie świadczą niezbicie o zbójnickiej przeszłości tego terenu. Nawet tutejszą kapliczkę lud nazywa zbójnicką, choć wybudowali ją górnicy, wydobywający rudy żelaza i metali kolorowych. W dolinie tradycyjnie gospodarzyli również pasterze. Kolorytu i wielu legend dostarczyli działający tu poszukiwacze skarbów.

Dolina Kościeliska ma wiele dolin bocznych, m.in.: Miętusia, Tomanowa, Pyszniańska, Smytnia czy też słynny wąwóz Kraków. Uroku i tajemniczości dodają temu miejscu liczne jaskinie, spośród których kilka udostępniono zwiedzającym.

Nazwa doliny pochodzi prawdopodobnie od kościółka, który jako jedyny w okolicy stał w Starych Kościeliskach. W przeszłości niektórzy miłośnicy mocnych wrażeń próbowali wywodzić pochodzenie nazwy tego miejsca od kości Tatarów, rozgromionych jakoby w XIII wieku. Nie wydaje się to prawdopodobne, choć dolina kryje wiele mrocznych wydarzeń. Tutaj popełniono na przykład pierwsze oficjalnie stwierdzone (w 1858 r. Kronika Parafii Zakopiańskiej) morderstwo. Ofiarą była ówczesna barmanka ze Starych Kościelisk, Marianna C., lat 50. Być może podała komuś nieświeżą strawę lub "ochrzczone" wino - sprawców nie wykryto.