When most people begin searching immigration records for ancestors, they think only of Ellis Island. This can be a mistake. Ellis Island was not the only passenger entry port and does not cover all the years that immigrants arrived in the United States. Failing to look beyond Ellis Island can lead to you hitting a brick wall with your genealogy research.
Before 1820, no records were kept of arrivals to the country. Starting in 1820, passenger names were recorded on the ship's passenger lists, but until 1855 passengers could just walk off the ship without any processing. Castle Garden was operated from 1855 to 1890 by the state of New York, at which point the federal government took over. Since Ellis Island was not completed yet, immigrants passed through the barge office until 1892 when Ellis Island was completed. Due to a fire on Ellis Island in 1897, the barge office was put back into operation until 1900.
Ellis Island then served as the immigration center until 1924. Then, passengers began being processed in the home country. There are limited Ellis Island records from 1924 to 1954, mainly for passengers of special circumstances.
Records prior to Castle Garden are available through the National Archives. There are several locations around the United States. You need microfilm series M237, rolls 1 through 94. You may also be able to view the microfilm at your local LDS Family History Center. If they don't have it available, you can usually request it from the main LDS Family History Library for a small fee.
You can search Castle Garden records for free from their website. It is important to note, however, that there are no manifest images available on the site and it may not have all the records.
New York was not the only port of arrival for immigrants. There were others. If you haven't been able to find your ancestors in Ellis Island or the records listed above, you may want to check these other ports.
Passenger Lists and Immigration Records 1820-1940s-This links to indexes to help you locate the appropriate microfilm, which can be viewed at the National Archives or LDS Family History centers. There are some links to paid databases, but they are marked as such. Ports covered include New York, Baltimore, Boston, Galveston, New Orleans and Philadelphia. There are also a couple links to other sites that may be helpful in your search.
Immigrant Ships Transcribers Guild-This is an excellent free genealogy resource for immigrants. While not every ship arrival is covered by the website, a great many are, with more being added on a regular basis. Choose a volume, then pick a port of arrival to get a list of all available transcriptions available. If you know the port of departure, but not arrival, you can also sort by that. Be sure to check back on a regular basis. Volunteers transcribe the records so it's possible the record you need has not been submitted yet.