Родился 28 июля 1953 г. в г. Моршанске Тамбовской области. Отец Борис Ефимович - замполит в радиотехническом полку; мать Таисия Никитична - ассистент фармацевта.
В 1970 г. поступил в Московский станкоинструментальный институт (ныне – Московский государственный технологический университет "СТАНКИН"), но обучение не завершил.
В 1976 г. окончил Омскую высшую школу милиции МВД СССР (ныне - Омская академия МВД России), позднее — Академию МВД СССР (ныне - Академия управления МВД России).
Доктор юридических наук. В 1999 г. в Российской академии государственной службы при президенте РФ защитил диссертацию на соискание степени кандидата юридических наук по теме "Взаимоотношения государственных органов исполнительной власти и органов местного самоуправления в сфере охраны общественного порядка и обеспечения общественной безопасности". В 2004 г. там же защитил докторскую диссертацию по теме "Специальные административно-правовые режимы в РФ".
С 1971 по 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 г. – Михаила Касьянова. В 1999-2000 гг. входил в состав президиума правительства РФ.
С 14 июня 1999 г. - член Совета безопасности РФ, с 28 марта 2001 по 9 марта 2004 г. - секретарь Совета безопасности РФ.
С августа 1999 г. участвовал в руководстве боевыми операциями федеральных войск против чеченских бандформирований на территории Дагестана и Чечни. С 15 сентября 1999 г. возглавлял Межведомственный оперативный штаб по противодействию терроризму.
В январе 2001 г. стал членом Оперативного штаба по управлению контртеррористическими действиями на Северном Кавказе.
9 сентября 2002 г. попал в автомобильную аварию на восьмом километре объездной дороги г. Петропавловск-Камчатский вместе с губернатором Камчатской области Михаилом Машковцевым. В результате столкновения автомашин пять человек погибли, девять человек были ранены и госпитализированы, в том числе Владимир Рушайло.
С 14 июня 2004 г. по 5 декабря 2007 г. - председатель исполнительного комитета, исполнительный секретарь Содружества независимых государств. Сменил на этом посту Юрия Ярова.
С 7 декабря 2007 г. по 25 сентября 2013 г. - член Совета Федерации РФ от законодательного органа власти Архангельской области. Входил в состав комитета СФ по правовым и судебным вопросам и комиссии СФ по вопросам развития институтов гражданского общества.
В августе 2008 г. был избран президентом Института международного права и экономики имени А. С. Грибоедова. В настоящее время является профессором кафедры "Конституционное и административное право", возглавляет наблюдательный совет института.
С 13 мая 2010 г. по 30 октября 2013 гг. - специальный представитель президента РФ по развитию отношений с Киргизией.
С 30 октября 2013 г. по 6 февраля 2019 г. - член правления, вице-президент публичного акционерного общества "Транснефть" (обеспечивает транспортировку около 90% добываемой в России нефти). Курировал вопросами безопасности. Акциями "Транснефти" не владел.
6 августа 2014 г. указом президента РФ Владимира Путина уволен с военной службы в отставку.
С 6 февраля 2019 г. - на пенсии.
Являлся членом Совета при президенте РФ по местному самоуправлению в 1999-2004 гг.
Генерал-полковник (1999).
Герой РФ (1999). Награжден орденами "Знак Почета" (1986), "За личное мужество" (1992), Мужества (1998); Почета (1998), "За заслуги перед Отечеством" III степени (2003). Отмечен почетными грамотами президента РФ (2012) и правительства РФ (2013).
Заслуженный работник МВД России.
Женат третьим браком, имеет троих детей. Старший сын Алексей (род. 1976), выпускник Академии ФСБ России, бывший сотрудник СВР России. Средний сын Андрей (род. 1980), выпускник Высшей школы милиции. Младший сын Илья (род. 1988), по данным СМИ, сотрудник Федеральной службы безопасности РФ.