Родился 28 июля 1953 г. в гор. Моршанске Тамбовской обл.
В 1970 г. поступил в Московский станкоинструментальный институт (ныне Московский государственный технологический университет "Станкин"), но обучение не завершил. В 1976 г. окончил Омскую высшую школу милиции МВД СССР (ныне Омская академия МВД России), позднее - Академию МВД СССР (ныне Академия управления МВД России, Москва).
Доктор юридических наук. В 1999 г. в Российской академии государственной службы при президенте РФ защитил кандидатскую диссертацию по теме "Взаимоотношения государственных органов исполнительной власти и органов местного самоуправления в сфере охраны общественного порядка и обеспечения общественной безопасности". В 2004 г. там же защитил докторскую диссертацию по теме "Специальные административно-правовые режимы в РФ".
С 1971 по 1972 г. Владимир Рушайло был рабочим, затем лаборантом в одном из московских научно-исследовательских институтов. С 1972 г. числился в органах внутренних дел СССР.
В 1976-1992 гг. работал в Московском уголовном розыске (МУР). Был сотрудником отдела по борьбе с квартирными кражами 4-го управления МУРа, с 1981 г. - отдела МУРа по раскрытию умышленных убийств, с 1986 г. - 6-го отдела по борьбе с бандитизмом и организованной преступностью, с 1988 по 1992 г. возглавлял этот отдел.
С марта 1992 г. являлся начальником службы по борьбе с организованной преступностью главного управления внутренних дел (ГУВД) Москвы.
В феврале 1993 г. стал начальником созданного по его инициативе регионального управления по организованной преступности (РУОП) ГУВД Москвы.
В том же году Владимир Рушайло добился вывода РУОП из подчинения ГУВД Москвы и их прямого подчинения главному управлению по организованной преступности (ГУОП) Министерства внутренних дел (МВД) России. В 1993-1996 г. занимал пост начальника РУОП по г. Москве - заместителя начальника ГУОП МВД РФ. 18 октября 1996 г. был назначен на должность первого заместителя начальника ГУОП МВД РФ.
22 октября 1996 г. Владимир Рушайло встретился с министром внутренних дел РФ Анатолием Куликовым и передал свой рапорт с просьбой вернуть его на прежнюю должность. После того как Куликов ему отказал, Рушайло выступил на пресс-конференции, где заявил, что не будет работать с первым заместителем министра внутренних дел РФ Валерий Петровым, которого обвинил в разрушении системы борьбы с организованной преступностью. В тот же день - 22 октября - Рушайло был отправлен в отставку.
С 9 декабря 1996 г. по 9 мая 1998 г. занимал должность советника председателя Совета Федерации Егора Строева по юридическим вопросам и безопасности.
С 9 мая 1998 по 21 мая 1999 г. был заместителем министра внутренних дел РФ Сергея Степашина - начальником главного управления по борьбе с организованной преступностью МВД России.
С 21 мая 1999 г. по 28 марта 2001 г. - министр внутренних дел РФ в правительствах Сергея Степашина, с августа 1999 г. - Владимира Путина, с мая 2000 г. - Михаила Касьянова (в 2023 г. включен в реестр иноагентов, в 2025 г. - в перечень террористов и экстремистов). В 1999-2000 гг. входил в состав президиума правительства РФ.
С 14 июня 1999 г. являлся членом Совета безопасности РФ. С 28 марта 2001 по 9 марта 2004 г. - секретарь Совета безопасности РФ.
С августа 1999 г. участвовал в руководстве боевыми операциями федеральных войск против чеченских бандформирований на территории Дагестана и Чечни. С 15 сентября 1999 г. возглавлял Межведомственный оперативный штаб по противодействию терроризму. В январе 2001 г. стал членом Оперативного штаба по управлению контртеррористическими действиями на Северном Кавказе.
С 14 июня 2004 г. по октябрь 2007 г. являлся председателем исполнительного комитета, исполнительным секретарем Содружества Независимых Государств (сменил на этом посту Юрия Ярова).
С 7 декабря 2007 г. по 25 сентября 2013 г. - член Совета Федерации (сенатор) - представитель от законодательного органа власти Архангельской области. Входил в состав комитета СФ по правовым и судебным вопросам и комиссии СФ по вопросам развития институтов гражданского общества.
В августе 2008 г. был избран президентом Института международного права и экономики им. А. С. Грибоедова (ныне Московский университет им. А. С. Грибоедова), являлся профессором кафедры "Конституционное и административное право", возглавлял наблюдательный совет института.
С 13 мая 2010 г. по 30 октября 2013 г. - специальный представитель президента РФ по развитию отношений с Киргизией.
С 30 октября 2013 г. по 6 февраля 2019 г. был членом правления, вице-президентом публичного акционерного общества "Транснефть". Курировал вопросы безопасности.
6 августа 2014 г. указом президента РФ Владимира Путина Владимир Рушайло был уволен с военной службы в отставку.
Являлся членом Совета при президенте РФ по местному самоуправлению (1999-2004).
Генерал-полковник (1999).
Награжден орденами "Знак Почета" (1986), "За личное мужество" (1992), Мужества (1998), Почета (1998), "За заслуги перед Отечеством" III степени (2003). Отмечен почетными грамотами президента РФ (2012) и правительства РФ (2013).
Герой РФ (1999).
Заслуженный работник МВД России.
Автор ряда научных трудов, учебных пособий и монографий.