Според „Българския етимологичен речник“ името произхожда от личното име Владай, запазено във влахо-българска грамота от 1577 година – сравнимо е старополското лично име Włodау. Името е прилагателно с наставка -ja, тоест Владаева (вьсь, тоест село) или родителен падеж от Владай – сравними са сръбското местно име Владаје, румънското Vlădaia и др. Възможно е и името да е направо от женското лично име Владая, запазено във влахо-българска грамота от 1610 г.За името Владая има легенди. Според едната легенда произлиза от глагола „владей“, а според другата е от времето на Второто българско царство (1185 – 1396) – от името на една от трите дъщери на цар (или на местен владетел): Яна, Бояна и Влада. И трите имена са използвани за наименования на области от Витоша.
При избухването на Балканската война през 1912 г. 2 души от с. Владая са доброволци в Македоно-одринското опълчение
В края на Първата световна война край селото се водят тежки боеве по време на Войнишкото въстание, наречено също Владайско въстание. Войските на въстаниците са ръководени от земеделския водач Райко Даскалов. През юли 1953 г. името на с. Владая е заменено от „Райко Даскалово“, но през 1962 г. е върнато на „Владая“.
По времето на социализма от 1972 до 1992 г. кмет на селото в продължение на 6 последователни мандата е Димитър Панев: всяка улица на селото е настлана с асфалт или паваж, направена е канализация (много важен фактор, който отличава с. Владая от другите селища в полите на Витоша); открива се стадионът на селото, дискотека с ресторант (по-късно е затворена), създаден е младежки танцов клуб в читалището. Последните 2 новости стават предпоставка за ежеседмични концерти както на най-известните за онова време естрадни певци – от Емил Димитров до Вили Кавалджиев, така и на известни рок и поп групи като „Тангра“, „Диана Експрес“ и др.
След промените и идването на демокрацията Панев е свален от поста. През 1999 г. той се кандидатира като независим и е избран за кмет отново. Във Владая на времето е имало пет кариери, които са произвеждали много голяма част от сиенитните павета на София, а в тях е работела и голяма част от населението на селото. Също има и завод за преработка на камъни „Мрамор Гранит“. Навремето е имало и фабрика за барут, която по-късно става химически завод с името „Красная звезда“ (днес има само малко останали постройки от нея).
Селото е обслужвано до 2011 г. от автобусна линия № 58, която впоследствие е слята с другата идваща от с. Мърчаево – № 59. Освен тези до селото достига и маршрутна линия 22, която изпълнява маршрут до ж.к. „Свобода“ (непосредствено до задния вход на стоковия базар в Илиянци).
