Backstreet Boys originated in Orlando , Florida and was formed on April 20 , 1993 by Lou Pearlman with the help of a producer , Lilâ Shy . Pearlman decided to call the group Backstreet Boys naming it after Orlando 's Backstreet flea market . The group had its very first performance at SeaWorld Orlando in May 1993 .