Earliest beginnings: 

The school we know today as the St. Paul's Institution was founded in 1899 by Father Catesson of the Paris Foreign Missions. Its aim was to provide an English education to "The boys of Seremban and its outstations". 
"St. Paul's School", as it was then called, was the first English school in the state. It was declared open on June 18 1899 by Sir Charles Mithchell, assisted by the British Resident for Negeri Sembilan, Mr. E.W. Birch. There was an initial enrolment of 25 students, accommodated in a provisional building under headmaster Mr. P.V. Coelho. Progress was satisfactory and the number of students steadily grew. 
 
Meanwhile, Father Catesson set about designing St. Paul's first permanent premises - a project brought to fruition by his successor, Father Nain. On August 19, 1907, the roofed building was officially opened by the High Commisioner, Sir John Anderson,. All 179 students moved into St. Paul's new $25,000 home. 

The Brothers come on the scene: 
  

The Christian Brothers' initial foothold in the region had been in Singapore and then Penang. Their good work there did not go unnoticed among the education authorities. 
As early as 1904, Rev Bro Gabriel, Visitor of the Christian Brothers' Schools, had been asked if the Order would take over St. Paul's. But demand for the Brothers was heavy - 1904 saw the establishment of St. John's Institution (SJI) in Kuala Lumpur - and there was no immediate response. 
In Seremban, all was not well. Mr. Coelho was an excellent Headmaster, but he was encountering great difficulty finding good teachers. Both the Mission and Mr. R.J. Wilkinson, the Federal Inspector of schools, saw the Brothers as the solution to St. Paul's woes.
Still, it was not till April 1st 1909 that urgent requests by the Bishop of Malacca and Director of Education finally fruit. Rev Bro Gilbert, Director of SJI, arrived in Seremban to take over St. Paul's on behalf of his Order. 
The school's rapid growth soon proved impractical the initial idea of long - distance supervision from Kuala Lumpur. Permanent on-the-spot management would be necessary, so Rev Bro Isidore-Albert was appointed Director. His tenure was short, for after about four-and-half months he was called to his reward. 
  

Expansion: 
  

The school, now called St. Paul's Institution, had 190 students when Rev. Bro. Basilian assumed the Directorship in January 1910. Contemporary accounts speak of "The Great Improvement In Educational Facilities" that followed the coming of the Brothers. In 1912, the first Senior Cambridge (Standard Nine) class achieved 100% pass rate. 
  A problem that now loomed large was the overcrowded state of the school. Student numbers were on the rise as demands for admission multiplied. Fr. Catesson's building no longer sufficed. Fortunately, the new Resident, Mr. R.J. Wilkinson, had taken great interest in St. Paul's when head of the Educational Department. A well known expert and author on Malayan subjects, he was well aware of the school's standard of instruments (which was graded in the first class by the Educational Department). 
  Thus, in 1911, the Resident submitted to the Federal Council an application for a Building Grant to enlarge the school premises. Sir Arthur Young, then High Commissioner, sanctioned a gift of $10,000 and a plot of land where Punca Emass Complex stands today. A further $10,000 was raised through the soliciting of donations, and construction duly proceeded. On September 26, 1912, , the Resident, Mr. A.H. Lemon opened a new eight-classroom block. Mr. Wilkinson's assistance received a special mention in the Brother Director's speech.

  From the First World War to the outbreak of the Second:  
  
 
In the years following 1994, when Rev. Bro. Adrian Edmund replaced Rev. Bro. Basilian, St. Paul's grew in several respects under a succession of the Directors. The acquisition of neighbouring buildings relieved the congestion in the original blocks, which were now reserved for residential purposes, offices and a library. 
Rev Bro Lewis Edward raised a temporary hall, made out of wood for concerts, assemblies and badminton. Bro Edward was a great sportsman-and in his day the St. Paul's Athletic Association (SPAA) won the premier state football trophy, the Hose Cup, for three straight years. A permanent school hall, along with modern toilets, was built during the Directorship of Bro. Joseph Brophy. He also purchased a large bungalow from Towkay Siow Kon Chia and a large shophouse in Jalan Tuan Sheikh for conversion into additional classrooms.