The history of the North Hollywood Amelia M. Earhart Regional Branch Library began in the early 1900's, as two bookcases in the corner of a City of Lankershim post office. As the library grew, it moved to a designated section within a feed store located at the corner of Lankershim Boulevard and Margate Street, and then to its own building on Margate next to the police station. On December 29th 1923, Lankershim was annexed to the City of Los Angeles, and the Lankershim library branch was turned over to the Los Angeles Public Library system in February of 1924. When the space on Margate became too small, the library moved to 5324 Bakman Street in August of 1927. That same summer, the City's name of "Lankershim" changed to "North Hollywood", and the Library Board changed the name of the Lankershim branch to the Sidney Lanier Branch. This name change was in keeping with the Los Angeles Public Library’s tradition in naming branches after literary figures. Sidney Lanier was born in 1842 in Georgia and was a well received Southern poet. Finally, on July 29th 1929, the library moved to its present location at 5211 Tujunga Avenue.

The original library building on Tujunga was constructed in 1929 by architects Eugene Weston and Eugene Weston Jr. in the Spanish Colonial Revival style. It's a one-story stucco Mission-style building with red and white-washed bricks, and a clerestory that contains seven multi-pane recessed windows. The upper roof is layered with red Spanish tiles, as is the lower roof; which is located below the clerestory windows and extends over a rectangular front porch. Two large coat-of-arms decorate either side of the clerestory, the left one a rendering of the Lanier family crest. An open-beamed interior ceiling enhances the Spanish character of the building, as do the stained glass windows at the building's entrance. Atop the fireplace is a display of hand-decorated Spanish styled tiles quoting poet Sidney Lanier with the words "I am a small-winged bird, but I can conquer the world". Another Sidney Lanier quote runs above the circulation desk in gold lettering saying "The earth: A grain of pollen dropped in the vast calyx of heaven". A third quote is etched into the pavement surrounding a plaza of plants that reads "The black birds giving a shimmer of sound, as midday transparent tremors of the heart and haze".

 Due to an unprecedented influx of people to the City of Los Angeles after World War II, steps had to be taken to accommodate high library usage and demand. The North Hollywood Sidney Lanier Branch was named as the Regional Branch for the San Fernando Valley in 1950, and housed that area office internally. Seven years later in 1957, the library celebrated a new addition that almost tripled its size. The architects who oversaw this project were John James Landon and Associates. They reconfigured and reorganized shelving and cabinetry, and brought in a large amount of new furniture. New reading areas, such as the teen alcove, were also included in this much-needed addition.

On November 12th 1980, a motion was passed by the Library Board of Commissioners to change the name of the library from the North Hollywood Sidney Lanier Regional Branch to the North Hollywood Amelia M Earhart Regional Branch. This request came from library patrons and local civic organizations interested in Amelia Earhart. The name change was particularly apropos because of the Amelia Earhart monument erected on the adjacent North Hollywood Recreation Center, years earlier.

On April 21st 1981, the North Hollywood branch was officially renamed in honor of the female aviatrix Amelia M. Earhart, who lived nearby in Toluca Lake at the time of her disappearance. One year later, on May 19th 1987, the branch was added to the National Register of Historic Sites in Los Angeles as part of a thematic group nomination of library branches that were built in revival styles, with the goal of preserving these institution's original structures.

When the 1994 Northridge quake hit the San Fernando Valley, many branches sustained sizeable damage and were closed until repairs could be made. During this time, the North Hollywood branch was adopted by MCA/Universal, one of the first partners with the Library Foundation in the Adopt-a-Branch program that assisted in providing funds for repairs. The Amelia Earhart Regional Branch was the last of these damaged branches to open, and after significant repairs and cosmetic improvements, celebrated the event on April 17th 1995. Two years later, on July 19th 1997, the newly improved library held a special celebration in honor of Amelia Earhart's 100th birthday.

By 2002, the library had become crowded once again. Through funding from Proposition DD, the 1998 Library Construction Bond, and funds from the City of Los Angeles' Seismic Bond and the Community Redevelopment Agency, M2A Architects and ARK Construction expanded and restored the 1929 building to it's original integrity. Renovations feature an addition of 1,400 square feet, reconfigured interior spaces that included a children's room, a new plaza, and a public parking lot, bringing the library facility to a total of 15,150 square feet. The addition was designed to blend seamlessly with the older structure while still maintaining some decorative modern updates, such as the four clay art friezes located in the reading room that were created by artist Beverly Crist depicting books and community. Following this update, in 2003 and 2004 the North Hollywood Amelia M. Earhart Regional Branch was awarded the State of California Governor's Design Award, the Los Angeles Conservancy Preservation Award, and the California Preservation Foundation Design Award.

Over the years, the branch has been a cultural gathering center for the community seeking information and enrichment. The library has been given donations to house a special collection on books on various aspects of aviation and women in aviation in particular, which has been dubbed the Amelia Earhart collection. Furthermore, the Amelia Earhart Regional Branch has received support from many local businesses and other organizations over the years, such as The Forest Lawn Foundation. Currently, the North Hollywood Amelia M. Earhart Regional Branch specializes in an extensive Russian language collection, as well as a Spanish language collection, in addition to the overall comprehensive programming, technology, and fiction and non-fiction collection in the adult, teen, and children's areas.