The prison was opened 25 March 1999 and is privately run by Serco (formerly known as Premier Prison Services) on behalf of the Scottish Prison Service; the first of its kind in Scotland.
The prison is operated to a contract between Serco and the Scottish Prison Service. This contract has a system of 44 performance measures, ranging from ensuring that prisoner's visitors are not unduly delayed on entrance to checking that appropriate levels of purposeful activities are provided to inmates.
In 2005 the BBC program Panorama uncovered several failings in the operational running of the prison, resulting in the prison carrying out internal investigations.
The prison, which holds short-term, long-term and remand male adults. The contract with the SPS means that HMP Kilmarnock currently holds on average 500 inmates. .