Billy´s career skyrocketed right from the start; within days he signed with Decca Records, recorded his first disc, the self penned "Maybe Tomorrow", which charted in February, spending 9 weeks on the charts, peaking at No. 18. By the end of April 1959 he had already made his television debut as an actor, playing a bit part in the ARTV play "Strictly For Sparrows" (plugging his first single, naturally), appeared on the television pop show "Cool For Cats" and made his radio debut on the BBC Radio show "Saturday Club". He also established himself as a regular on Jack Good´s legendary "Oh Boy!" television show. His second single, "Margo", also his own composition, only reached No. 28 and the next two singles failed to chart completely, probably as a result of bad press which he was receiving, because of his wild and overtly sexual stage act. On October 30th at the Theatre Royal, Dublin, the curtain was dropped during his act. That sort of exhibitionism wasn´t appreciated by Britain´s Watch Committee and they tried to have Billy banned from the nation´s stages. Eventually Billy capitulated and cleaned up his act. By that time Furymania had reached such heights that he couldn´t go anywhere without being recognised. And pretty soon it reached to a point where he became a prisoner of fame; he had to be smuggled from the hotel to the theatre and back to the hotel, from one town to another.
During the last months of the decade Billy appeared several times on Jack Good´s latest pop vehicle "Boy Meets Girl", a TV show where American rock´n´rollers Gene Vincent and Eddie Cochran made their UK debuts. On January 24,1960, Larry Parnes´ latest rock spectacular "The Fast Moving Anglo-American Beat Show", a 12-week, twice nightly, UK tour, started at the Gaumont Theatre, in Ipswich, Gene Vincent and Eddie Cochran headlining. Also on the bill with Billy, Joe Brown, Tony Sheridan Trio, Georgie Fame and Billy Raymond. The tour ended in tragedy when Eddie Cochran got killed in a car accident while on his way to the airport and back home to the US. In March, while Billy was still on the road with the Americans, his fifth single "Colette" entered the Hit Parade, spending 10 weeks on the charts and reaching the number 9 spot - so far his biggest hit.
Encouraged enough by the sales of "Colette", Decca planned for a 10 inch LP, "The Sound Of Fury", recorded in April 1960, with Jack Good handling the production. The album contained ten songs, all written by Billy, some of them under pseudonym Wilbur Wilberforce, and was the first real British rockabilly record. The album and a single "That´s Love" lifted from it, both made the charts in June, the album reaching the 18th place and the single the 19th place at it´s best. On May 10th, the Beatles among other Liverpool bands auditioned for Parnes and Billy, at Wyvern Social Club, in Liverpool, trying to get a break as Fury´s backing band. However, this never happened - instead Billy made a short tour with Cass & the Casanovas By that time Billy had also hosted Jack Good´s latest TV show, the short-lived "Wham!" The rest of the year Billy toured with Joe Brown and other stable mates in a Larry Parnes/Jack Good production "The Rock´n´Trad Spectacular" (subtitled as "The New Noise Of 1960"), a sort of stage version of Good´s TV shows where as many performers as possible were squeezed in and each having their own 30 minutes in the spotlight. Jack Good also produced Billy´s next single "Wondrous Place", a great number when performed live and one of Billy´s personal favourites; he recorded five versions of the song during his recording career. Despite being a great song it didn´t climb higher than No. 25 in the charts during November.
The year 1961 started with a cover of the Rivileers´ "A Thousand Stars" and Marty Robbins´"Don´t Worry", both reaching the tail end of the charts, but it was "Halfway To Paradise" that really made him a major star. The Goffin/King song had been a minor hit in the US for Tony Orlando, but Billy´s cover is now considered the definitive version. It entered the charts in May and stayed there 23 weeks, peaking at No. 3, earning Billy a Silver Disc for passing the 250,000 sales mark in August. This was the first session produced by Dick Rowe and Mike Smith for Billy, with Ivor Raymonde in charge of musical direction - a combination that would produce most of Billy´s big hits. While the single was racing up the charts, an LP was hurriedly assembled and issued through Decca´s subsidiary label Ace of Clubs. The follow-up was an old standard "Jealousy", released in September and reaching No. 2 in the next month, the closest Billy Fury ever came to the top spot in the UK. Another Goffin/King song proved to be a huge success for him; "I´d Never Find Another You" was released in November, eventually reaching 5th place in the charts and in January it had sold over 250,000 copies, earning Billy his second Silver Disc and also the Carl-Alan Award from Mecca Dancing when this was voted the most popular record at Mecca Ballrooms all over the UK. More awards kept pouring in; Billy was voted Britain´s No. 3 Male Singer in annual New Musical Express´ poll, just behind Adam Faith and Cliff Richard, and was No. 1 Most Requested Artist for Poll Concert, an award which he was to receive for the next two years, validating his position as most exciting live performer. It was also during this time that Billy had his own 30-minute show "The Sound Of Fury" on Radio Luxembourg and he won the Getaway Trophy on the programme´s "Battle Of The Giants" competition in 1962 and 1966. At the end of 1961 Billy scored an overwhelming success at the famous Olympia Theatre in Paris, France.