First restart the phone (turn it off and back on). Then try the touch and hold the background of the home screen again. It should bring up the screen that has icons, widgets, etc. If it doesn't then try going to the direct icons list (usually an icon with little squares) and it will be there.
Now, you also may not have deleted the icons. They could have been moved to other home screens, and they could have been combined with other icons to make a folder. So I would check that as well.