The new relegation to the lower tier after the unsuccessful 1958/1959 season was not taken tragically. The club had a good generation of young players from whom real results were yet to be expected. Promotion to the First Division eluded them by a hair. However, the third time was the charm, as the first place in the 1961/1962 season brought a return to the First Federal League. Led by Vlatko Konjevod from the bench, and on the field with Osim, Smajlović, Radović, Kokot, Kulović, and others, the “Blues” won the first place in front of Sloboda from Tuzla on goal difference. It was the birth of a team that would mark Sarajevo, Bosnia and Herzegovina, and Yugoslav football in the transition from the sixties to the seventies of the 20th century.
The potential of this team was evident from the very beginning, as they secured an excellent third place in their first season after returning to the First Federal League. This achievement marked Željezničar’s greatest success so far and earned them their first appearance in a European competition – the then Mitropa Cup. The team played beautifully and earned many convincing victories. Mišo Smajlović was also the top scorer of the championship, while their performances in Europe were noteworthy, particularly their win against the formidable Austria from Vienna. However, MTK from Budapest proved to be too great of an obstacle, as Hungarian football was among the strongest in the world at that time.
Similar play will be seen in the coming seasons. The placement in the first part of the table in the competition of other strong clubs was a hint of what is to come. There were new players at the club, upcoming stars such as Katalinski, Hadžiabdić, Bukal, Bratić, Spreča, Mujkić, and others, complementing the already respectable composition of the blue team. When the first team was taken over by the coaching staff led by Milan Ribar in the following season, the last dice was stacked. The locomotive was moving forward.
During this period, Željezničar played its home games at the Grbavica stadium. However, the wooden construction violated safety standards, so it was decided to begin reconstruction. Therefore, in the summer of 1968, Željezničar temporarily moved to the city stadium Koševo, where they would play for the next eight years and achieve great results. During this time, new facilities were built at Grbavica, including concrete stands along the east and south sides of the field.
Getting involved in the so-called “Big Four” was extremely difficult. These were the clubs that dominated domestic football year after year, and financially they were much better and able to attract the best players from other regions without any problems. Raising their own strengths was the only possible way for others to oppose them with quality. That’s exactly what Željezničar did. The future stars of European football grew in Grbavica, and with each season, they only reaffirmed their potential. In the 1969/1970 season, we were three points away from first place. A season later, we came in second, with a four-point difference behind Hajduk. But all of this was just a prelude to what followed.