用人单位不能仅因您有犯罪史就随意解除劳动合同，是否合法解除需分情况判断，您可按以下步骤处理：
- 核查用人单位解除依据是否合法
根据《劳动合同法》第39条，用人单位仅在劳动者“被依法追究刑事责任”时，可无需支付经济补偿直接解除合同。但需注意：
- “被追究刑事责任”的界定：指被法院判处刑罚（包括管制、拘役、有期徒刑等），或被检察院免予起诉、被法院免予刑事处分的情况。若您仅曾被刑事拘留、逮捕或存在犯罪记录但未被最终定罪（如撤案、不起诉、无罪判决），则不属于法定解除情形。
- 用人单位需举证：若用人单位主张解除合同，必须提供法院生效裁判文书等证据证明您“被追究刑事责任”，否则构成违法解除。
- 若用人单位解除违法，您可主张权利
若用人单位无法证明解除合法性，您可采取以下措施：
- 要求继续履行合同：若您仍希望保留工作，可书面要求用人单位撤销解除决定、恢复劳动关系，并补发解除期间的工资。
- 主张赔偿金：若您不希望继续工作，可要求用人单位支付违法解除赔偿金（标准为经济补偿金的2倍，即工作每满1年支付2个月工资）。
- 申请劳动仲裁：若协商无果，需在知道被解除之日起1年内向劳动仲裁委提起仲裁，提交劳动合同、解除通知、犯罪记录证明（若用人单位以此为由）等证据。
- 特殊情形：涉及职业禁入规定
若您曾犯的罪与现岗位存在直接关联（如财务岗位犯贪污罪、教育岗位犯性侵罪），且法律、行政法规明确禁止从事该职业（如《教师法》规定“受到剥夺政治权利或故意犯罪受到有期徒刑以上刑事处罚的，不能取得教师资格”），则用人单位解除合同可能被认定为合法。但需注意：
- 禁入规定需明确：必须由法律、行政法规作出规定，地方性法规或单位内部规定无效。
- 岗位匹配性：需证明犯罪与岗位存在直接、必然的联系（如司机岗位犯危险驾驶罪）。
行动建议：
- 立即要求用人单位出具书面解除通知，明确解除理由；
- 核查自身犯罪记录是否属于“被追究刑事责任”及是否涉及职业禁入；
- 收集劳动合同、工资记录、解除通知等证据；
- 优先与用人单位协商，协商不成及时申请劳动仲裁。
若您需要进一步分析具体案情或协助准备仲裁材料，可随时向我提供更多细节（如犯罪类型、用人单位解除理由、岗位性质等），我会为您制定针对性方案。