โครงการเวลิบได้รับการริเริ่มโดย แบร์ตรองด์ เดอลาโน (ฝรั่งเศส:Bertrand Delanoë) นายกเทศมนตรีเมืองปารีส จากพรรคสังคมนิยม (ฝรั่งเศส: Parti socialiste, PS) เริ่มให้บริการครั้งแรกเมื่อวันที่ 15 กรกฎาคม พ.ศ. 2550 โดยบริษัท JCDecaux บริษัทธุรกิจโฆษณาเป็นผู้ดำเนินโครงการเป็นเวลา 10 ปี หลังจากสามารถชนะการประมูลกับบริษัท Clear Channelภายหลังโครงการ Vélo'v ซึ่งเป็นระบบให้เช่ายืมจักรยานสาธารณะของนครลียง (ฝรั่งเศส: Lyon) ซึ่งเริ่มให้บริการตั้งแต่ปี พ.ศ. 2548

ในระยะแรก เวลิบให้บริการด้วยจักรยานจำนวน 7,000 คัน สถานียืมคืนอัตโนมัติ 750 แห่ง และเพิ่มเป็น 16,000 คัน และ 1,200 สถานีในปีถัดมา ในปีแรก เทศบาลเมืองปารีสรายงานว่ามีผู้ใช้บริการ Vélib ถึง 27.5 ล้านเที่ยว โดยผู้ใช้บริการกว่า 2.1 ล้านคน[1]