The Palace Theatre & Grand Hall Complex is a multi-purpose entertainment arena complex in Green Street, Kilmarnock, Scotland. The structure, which was originally opened as a corn exchange, is a Category A listed building.

In the mid-19th century, a group of local businessmen formed a company, The Corn Exchange Company, to finance and erect a corn exchange for the town. The site they selected on Green Street had originally been a public bleaching green before being occupied by the local fish market.

The Corn Exchange opened on 16 September 1863 and served as the principal business space in Kilmarnock for farmers and merchants. The facade of the building is dominated by a 110-foot-tall clock tower which was named in order to commemorate Prince Albert, the Prince Consort, who died in 1861. To allow for the construction of the tower to take place, the tower was funded through a public subscription of £600. After securing funds, the clock was designed and constructed by John Cameron, jeweller and watchmaker situated on King Street. The sculpted heads over the main entrance represent Prince Albert, Sir James Shaw, the Kilmarnock-born Lord Mayor of London, and Lord Clyde, a Scottish hero of the Crimean War and Indian Mutiny.

The ground floor of the Corn Exchange which looked towards Green Street consisted of a number of shops and also housed a public library on the upper floor of the building. The upper floor which faces towards London Road contained the Athenaeum reading room. The final cost for the construction of the Corn Exchange was estimated to be just over £6,000. The opening of the Corn Exchange was commemorated by two performances conducted by the Kilmarnock Philharmonic Society of Judas Maccabaeus (Handel) by Thomas Morell. Other events to mark the occasion were a ball for 200 persons and a celebration dinner for 350.

It was always originally intended that the Corn Exchange was also to be a place of entertainment, as well as business, and it was available for concerts, bazaars, political meetings and other activities. The main hall of the Corn Exchange could accommodate 1,200 people, and the main hall also housed a pipe organ at one end of the hall.

The building was designed by James Ingram in the Italianate style, built in red sandstone and was officially opened on 16 September 1863. The design involved an asymmetrical main frontage on the corner of London Road and Green Street. It featured a four stage tower, known as the "Albert Tower", at the corner with wings of nine bays extending down London Road and of thirteen bays extending down Green Street. The tower featured three round headed doorways in the first stage, three round headed windows with architraves, keystones and a balcony in the second stage, the burgh coat of arms and a cornice inscribed with the motto "The Earth is the Lords and the Fullness Thereof" in the third stage, and a belfry in the fourth stage, all surmounted by a dome. The wings were fenestrated by segmental headed windows on the ground floor and by round headed windows with architraves and keystones on the first floor. At roof level, the wings were surmounted by balustraded parapets which were decorated by urns.

The building was extended along London Road by extra eight bays to a design by Robert Ingram in 1886. The use of the building as a corn exchange declined significantly in the wake of the Great Depression of British Agriculture in the late 19th century, and it was therefore converted into a music hall in 1903.

In the 1940s, extensive internal alterations were carried out to a design by Gabriel Steel to create the Grand Hall.

The first films were shown at the Corn Exchange as early as 1897, and by 1911, they were a regular feature of the programme of entertainment offered at the venue. By the 1930s, the venue had become used exclusively a cinema under the name Palace Picture House. A state- of-the-art sound system was installed in order for the new ‘talkies’ system to be used which saw a recording of the film soundtrack being played over a gramophone which was synchronised with the projector.

Following World War II, the Palace Picture House failed to compete with more modern and more comfortable cinemas in Kilmarnock, such as the Regal Cinema and the Plaza. As a result, it closed in 1949.

The venue was vacant until a gift of £5,000 towards its refurbishment prompted the Council to spend a further £30,000 in order to redevelop the venue and bring it back into public use. By 1951, the venue re–opened as the 625-seater Exchange Theatre, with Mr Kurt Lewenhak being appointed manager of the Exchange Theatre, at a salary of £650. Originally, The Exchange was intended to be a civic theatre that would feature programmes which would showcase local talent. Early shows included the Kilmarnock Amateur Opera Society’s production of Rio Rita, the Saxone Dramatic Club’s production of Allan Ramsay’s 1725 play The Gentle Shepherd, Kilmarnock Combined Dramatic Clubs’ production of Dear Brutus, and Henry Cotton’s Golf Show. The first major production was a variety show entitled Merry-go-Round – ‘the show with a swing to it’ which opened on 20th June 1951, and ran for a total of eight weeks with regular changes of content. Despite a successful opening night, the show was deemed to be unsuccessful and saw the Exchange Theatre operating on a loss of an average of £372 a week.

In 1979, the theatre was severely damaged by fire, and eventually re–opened to the public on 4 September 1982 following a programme of repairs costing £190,000, with a variety show for charity starring Johnny Beattie, Joe Gordon and Sally Logan. Following further improvements, the Palace was formally re-opened on 31 August 1985 by comedian Billy Connolly.

In December 2023, the Palace Theatre closed temporarily in order for the complex to undergo restoration work as part of the Cultural Kilmarnock Project following allocation of £20 million in funding from the UK Government as part of the Levelling Up Programme funds, along with the Dick Institute and the Grand Hall. The project consists of a process of major reimagining of the Palace Theatre and Grand Hall in order to create a "regional concert hall and theatre with extensive improvements to the accessibility and energy efficiency".

The glam rock band The Sweet wrote their song "The Ballroom Blitz" about an incident, in January 1973, when they were bottled off the stage during a performance in the building. After a serious fire in 1979, the building was restored and re-opened by Billy Connolly in August 1985. In 2022, the Grand Hall hosted an episode of the 2022 BBC New Comedy Award.

The Palace Theatre and/or the Grand Hall has played host to shows by the following: