ในปี ค.ศ. 1904 สองพี่น้อง แซมและวูล์ฟ วอลด์บอม ผู้อพยพชาวยิวจากแคว้นกาลิเซียของยูเครน ได้เปิดร้านค้าในบรูคลิน หลานชายของพวกเขา อิสราเอล "อิซซี่" วอลด์บอม เดินทางมายังอเมริกาและเข้าร่วมธุรกิจ ชายทั้งสามคนบริหารร้านค้า โดยอิซซี่รับช่วงต่อกิจการขายของชำเมื่อลุงของเขาเกษียณ อิซซี่แต่งงานกับจูเลีย เลฟเฟล และมีลูกสามคน^{[ 3 ]}บริษัทสร้างประวัติศาสตร์ในปี ค.ศ. 1938 เมื่อ พี่น้อง ฝาแฝดเออร์เนสต์และจอร์จ บราวน์ ซึ่งเริ่มต้นทำงานที่ร้านค้าเพียงสองแห่งที่มีอยู่ในขณะนั้นในตำแหน่งเด็กยกของ ได้รับการเลื่อนตำแหน่งเป็นเด็กคิดเงิน "ในตอนนั้นเป็นเรื่องที่ไม่เคยเกิดขึ้นมาก่อนที่พนักงานคิดเงินผิวสีจะอยู่ในย่านคนผิวขาว" เออร์เนสต์ บราวน์ กล่าวในการสัมภาษณ์เมื่อสามทศวรรษต่อมา ต่อมาทั้งสองคนได้เป็นผู้จัดการร้าน และในที่สุดก็เป็นผู้บริหารของวอลด์บอม (รองประธานและผู้ช่วยรองประธาน ตามลำดับ) ^{[ 4 ]}

เมื่ออิซซี่เสียชีวิตในปี 1948 ลูกชายของเขา อิรา วอลด์บอม ได้ลาออกจากการศึกษาที่มหาวิทยาลัยนิวยอร์กและเข้ารับช่วงต่อกิจการร้านค้าทั้งหกแห่งของบริษัทในบรูคลิน^{[ 3 ] [ 5 ]}จูเลีย วอลด์บอมภรรยาของอิซซี่มีบทบาทอย่างแข็งขันในบริษัทและดำรงตำแหน่งเลขานุการ ตั้งแต่ทศวรรษ 1960 เป็นต้นมา รูปภาพและสูตรอาหารของเธอปรากฏอยู่บนผลิตภัณฑ์ภายใต้แบรนด์ของบริษัทเกือบทั้งหมดกว่า 400 รายการ^{[ 6 ]}

ในปี พ.ศ. 2494 บริษัทได้เปิดซูเปอร์มาร์เก็ตแห่งแรกในฟลัชชิง ควีนส์และยอดขายสุทธิสูงถึง 55.2 ล้านดอลลาร์ในปี พ.ศ. 2503 ในปี พ.ศ. 2504 บริษัทได้เข้าจดทะเบียนในตลาดหลักทรัพย์โดยการขายหุ้นสามัญ แม้ว่าตระกูลวอลด์บอมยังคงเป็นเจ้าของหุ้นส่วนใหญ่^{[ 7 ] [ 8 ]}ในเวลานั้น วอลด์บอมมีร้านค้า 25 แห่งและมียอดขาย 80 ล้านดอลลาร์ ในปี พ.ศ. 2513 บริษัทได้ซื้อกิจการเครือข่ายฟู้ดมาร์ทในคอนเนตทิคัตและแมสซาชูเซตส์^{[ 5 ] [ 8 ]}

เมื่อวันที่ 2 สิงหาคม พ.ศ. 2521 มีรายงานเหตุเพลิงไหม้ที่ร้านค้าแห่งหนึ่งในSheepshead Bay, Brooklynซึ่งกำลังอยู่ระหว่างการปรับปรุง หลังคาถล่มลงมาขณะที่นักดับเพลิงพยายามระบายอากาศออกจากอาคาร ทำให้นักดับเพลิงเสียชีวิต 6 นาย และบาดเจ็บกว่า 30 นาย^{[ 9 ] [ 10 ]}พนักงานสอบสวนจับกุมชายหนุ่มวัย 21 ปี ชื่อ Eric Jackson ซึ่งถูกตั้งข้อหาลักลอบวางเพลิงและฆาตกรรม 6 กระทง เขาถูกตัดสินว่ามีความผิดและถูกจำคุก 25 ปีถึงตลอดชีวิตในเรือนจำของรัฐ อย่างไรก็ตาม หลักฐานในภายหลังแสดงให้เห็นว่าเพลิงไหม้เกิดจากความผิดพลาดทางไฟฟ้า และอัยการได้ปกปิดข้อมูลจากทีมทนายความฝ่ายจำเลยและสร้างหลักฐานเท็จเพื่อใส่ร้าย Jackson ^{[ 11 ]}ในปี พ.ศ. 2531 มีการสั่งให้พิจารณาคดีใหม่ และในปี พ.ศ. 2537 คณะลูกขุนได้ตัดสินให้เขาพ้นผิด^{[ 12 ] [ 13 ]}

ในเดือนมีนาคม พ.ศ. 2522 ร้าน Waldbaum's ใน ย่าน East Flatbushของบรูคลินถูกปล้นโดยใช้อาวุธ คนร้าย 3 คนจับลูกค้า 40 คนไว้ในร้านเป็นเวลา 3 ชั่วโมงครึ่งก่อนจะยอมจำนนต่อตำรวจ^{[ 14 ] [ 15 ]}

ในปี พ.ศ. 2527 Waldbaum's ยอมรับผิดในข้อหาสมรู้ร่วมคิดในการกำหนดราคา หลังจากที่บริษัทถูกกล่าวหาว่าสมรู้ร่วมคิดกับPathmarkและKing Kullenในการส่งเสริมการขายแบบ"คูปองสองเท่า" ร่วมกัน ^{[ 16 ]} Waldbaum's จ่ายค่าปรับ 700,000 ดอลลาร์^{[ 8 ]}หลังจากทำการโฆษณาภายในองค์กรมาหลายปี ในปี พ.ศ. 2531 บริษัทได้ว่าจ้างD'Arcy Masius Benton & Bowlesซึ่งเป็นบริษัทโฆษณา ด้วยงบประมาณ 5 ล้านดอลลาร์^{[ 17 ]}

ในเดือนพฤศจิกายน พ.ศ. 2529 บริษัท Waldbaum's ได้ขายหุ้นส่วนใหญ่ของบริษัทให้กับบริษัท The Great Atlantic and Pacific Tea Company หลังจากการขาย ครอบครัว Waldbaum ยังคงบริหารจัดการร้านค้าต่อไป^{[ 7 ]}

ในปี 1989 Waldbaum's ได้เปิดบริการสั่งซื้อถึงบ้าน โดยลูกค้าสามารถโทรสั่งสินค้าและรับสินค้าได้^{[ 18 ]}ในเดือนมกราคม 1996 มีผู้ได้รับบาดเจ็บ 14 คน เมื่อหลังคาของร้าน Waldbaum's ในเมือง Massapequa รัฐนิวยอร์กพังถล่มลงมาเนื่องจากน้ำหนักของหิมะในช่วงพายุหิมะครั้งประวัติศาสตร์ในปี 1996 ^{[ 19 ] [ 20 ]}

หลังจากการซื้อกิจการ Pathmark ในปี 2550 A&P จำเป็นต้องขายสาขา Waldbaum's จำนวน 5 แห่งใน Staten Island และ Long Island เพื่อให้เป็นไปตามข้อกำหนดของหน่วยงานกำกับดูแลเกี่ยวกับข้อกังวลด้านการต่อต้านการผูกขาด^{[ 21 ] [ 22 ]}

ในเดือนสิงหาคม พ.ศ. 2553 A&P ประกาศว่าจะปิดร้านค้า 25 แห่ง เนื่องจากบริษัทแม่ของ Waldbaum's เริ่มดำเนินการตามแผนฟื้นฟูธุรกิจอย่างครอบคลุม^{[ 23 ]}ในเดือนกันยายน A&P ประกาศแผนการเลิกจ้างพนักงานกว่า 400 คน รวมถึงพนักงาน 195 คนจากการปิดร้าน Waldbaum's ในWest Hartford รัฐคอนเนตทิคัต ^{[ 24 ] [ 25 ]}ร้านค้าใน Centereach และ Levittown ปิดตัวลงในเดือนตุลาคม^{[ 26 ] [ 27 ]}

ในเดือนธันวาคม พ.ศ. 2553 A&P ยื่นขอล้มละลาย^{[ 28 ] [ 29 ]}เพื่อช่วยฟื้นฟูธุรกิจ A&P ได้ระบุสถานที่ 32 แห่งที่จะปิดตัวลง รวมถึงร้านค้าของ Waldbaum ใน Farmingdale, Smithtown และ Valley Stream ^{[ 30 ] [ 31 ]}

ในเดือนมกราคม พ.ศ. 2555 A&P ประกาศว่าจะปิดร้านค้าอีก 6 แห่งใน Commack, West Babylon, East Islip, Lake Ronkonkoma, Huntington Station และ Rockville Centre ^{[ 32 ]}บริษัทแม่ของ Waldbaum พ้นจาก การคุ้มครองการล้มละลายตาม บทที่ 11ในฐานะบริษัทเอกชนในเดือนมีนาคม พ.ศ. 2555 ^{[ 33 ]}

เมื่อวันที่ 20 กรกฎาคม 2558 A&P ได้ยื่นขอฟื้นฟูกิจการภายใต้บทที่ 11 หลังจากประสบกับภาวะขาดทุนทางการเงินมาหลายปีและต้องดิ้นรนเพื่อแข่งขันกับร้านค้าปลีกขายของชำคู่แข่ง^{[ 34 ] [ 35 ]}ร้าน Waldbaum's สามแห่งใน Carle Place, Riverhead และ Oceanside มีกำหนดปิดตัวลง^{[ 36 ]}

บริษัทประกาศความตั้งใจที่จะขายร้านค้า 120 แห่งทันทีStop & Shopซื้อสาขาของ Waldbaum ใน Bedford, East Hampton, Southampton, Baldwin, Massapequa, Long Beach, Huntington, Howard Beach, Belle Harbor และ Bay Terrace ^{[ 37 ]} Key Foodซื้อร้านค้าใน Moriches, Mattituck, Albertson, Flushing, Glen Head, Brooklyn, Jackson Heights, Glen Oaks และ Bayside ^{[ 38 ] [ 39 ]}ร้านค้า 5 แห่งถูกขายให้กับBest Yet Marketในเดือนพฤศจิกายน 2015 ^{[ 40 ]}และอีก 3 แห่งถูกขายให้กับWakefern Food Corporationเจ้าของเครือ ShopRite Foodโดยมีหน่วยงานอื่นๆ อีกหลายแห่งเข้าซื้อสาขาเพิ่มเติม^{[ 41 ] [ 42 ]}

ร้านค้าทั้งหมดของ Waldbaum ถูกขายหรือปิดตัวลงภายในเดือนพฤศจิกายน 2015 ^{[ 42 ] [ 43 ]}ในเดือนธันวาคม 2018 บริษัทไพรเวทอิควิตี้ American Legacy Brands ได้ซื้อสิทธิ์ในทรัพย์สินทางปัญญาของ A&P และ Waldbaum โดยมีเจตนาที่จะอนุญาตให้ใช้ชื่อดังกล่าวสำหรับสินค้าภายใต้แบรนด์ของตนเอง^{[ 44 ] [ 45 ]}